FIG. 1 shows a conventional transform encoder 10 having a structure common to many well-known audio, video and image coding standards. This common encoder structure includes a linear transform 12, a scalar quantizer 14, and an entropy coder 16, arranged in that order. Transform coding of this type is generally viewed as a computationally efficient alternative to vector quantization. At high encoding rates, it is typically not the transform partitioning itself but the efficiency of the entropy coder that makes transform coding most useful. In the transform encoder 10, the transform is calculated on continuous-value data, i.e., "full precision" data prior to quantization, even though the data will ultimately be represented more coarsely. This also tends to increase the complexity of the subsequent entropy coding operations. Although developments such as zero-tree structures, described in J. M. Shapiro, "Embedded image coding using zero trees of wavelet coefficients," IEEE Trans. Signal Proc., 41(12):3445-3462, December 1993, mix the quantization and entropy coding operations to some degree, the transform is generally still calculated on continuous-value data.
In traditional transform coding of the type illustrated in FIG. 1, the input is generally a continuous-valued random vector sequence x, and it is presumed that the entropy coder 16 uses scalar entropy coding. The problem is then to design a continuous-valued linear transform T such that x=Q(T(x)) is coded efficiently with scalar entropy coding, where x=(x.sub.1, x.sub.2, . . . x.sub.n) is a discrete-valued random vector and Q is a scalar quantization function. The average rate for entropy coding of x is lower bounded by the entropy: H(x).ltoreq.R(x), where H(.cndot.) denotes the entropy of a random variable and R(.cndot.) denotes the rate obtained with an actual code. Subscripts on R will be used herein to distinguish between specific codes, when necessary. In addition, there is always a code that performs within one bit of the entropy, i.e., R(x)&lt;H(x)+1. A Huffman code is an example of one such code.
Scalar entropy coding separately encodes each of the n components of x. This separate encoding can reduce the memory requirements and encoding complexity in many applications, but may also result in an increase in encoding rate. There are two causes of this increase. First, the dependencies between components may not be completely exploited. This is reflected by the following basic property of entropy: ##EQU1##
Second, when using an entropy code, one may do as much as one bit worse than the above-noted entropy bound, i.e., R.sub.0 (x).ltoreq.H(x)+1. Thus, using n separate codes may waste n bits: ##EQU2##
In the above-described traditional transform coding framework, the conventional approach is to pick the continuous-valued linear transform T from among a set of orthogonal transforms, as described in, e.g., A. Gersho and R. M. Gray, "Vector Quantization and Signal Compression," Kluwer Acad. Pub., Boston, Mass. 1992. Use of a nonorthogonal transform would generally make the quantizer less effective. Among the orthogonal transforms, there is an essentially unique transform, known as a Karhunen-Loeve transform, that minimizes the rate after scalar entropy coding. It was observed in M. T. Orchard et al., "Redundancy Rate-Distortion Analysis of Multiple Description Coding Using Pairwise Correlating Transforms," Proc. IEEE Int. Conf. Image Proc., Vol. 1, pp. 608-611, Santa Barbara, Calif., October 1997, that if a continuous-valued vector x with independent components is first quantized and then transformed, i.e., such that x=T(Q(x)), then there is no need to limit the set of transforms. Generalizations to arbitrary dimension transform coding in the multiple description transform context are described in U.S. patent application Ser. No. 09/030,488 filed Feb. 25, 1998 in the name of inventors Vivek K. Goyal and Jelena Kovacevic and entitled "Multiple Description Transform Coding Using Optimal Transforms of Arbitrary Dimension."
The above-described conventional approaches can suffer from significant drawbacks. For example, in traditional transform coding, all of the degrees of freedom in the design are generally used to minimize the rate, with the result that no degrees of freedom are left for other manipulations.
It is therefore generally not possible, using the conventional transform coding techniques described above, to minimize the entropy coding rate and simultaneously pursue other important objectives such as memory reduction. Conventional encoding techniques are therefore unduly complex, and often consume excessive storage and computational resources.